|On Chubanov's method for Linear Programming - Amitabh Basu|
We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos, and Vavasis and Ye.
|Unique Minimal Liftings for Simplicial Polytopes - Amitabh Basu|
For a minimal inequality derived from a maximal lattice-free simplicial polytope in $\R^n$, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers $\R^n$. We then use this characterization to show that a minimal inequality derived from a maximal lattice-free simplex in $\R^n$ with exactly one lattice point in the relative interior of each facet has a unique minimal lifting if and only if all the vertices of the simplex are lattice point...
|Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets - Amitabh Basu|
We study a mixed integer linear program with m integer variables and k non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [Inequalities from two rows of a simplex tableau, Proc. IPCO 2007, LNCS, vol. 4513, Springer, pp. 1--15]. We describe the facets of this mixed integer linear program via the extreme points of a well-defined polyhedron...
|Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming - Amitabh Basu|
Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability...
|Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two-Dimensional Case - Amitabh Basu|
We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem.
|The Triangle Closure is a Polyhedron - Amitabh Basu|
Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron...
|On the sufficiency of finite support duals in semi-infinite linear programming - Amitabh Basu|
We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash [Linear programming in infinite dimensional spaces : theory and applications, Wiley 1987]...
|A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation - Amitabh Basu|
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.